package acwing;

import java.io.*;
import java.util.Arrays;

public class A849 {
    static BufferedReader read=new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log=new BufferedWriter(new OutputStreamWriter(System.out));
    static int N=510;
    static int [][] g= new int[N][N];
    static int[] dist=new int[N];
    static boolean[] st=new boolean[N];
    static int n;
    static int m;
    public static void main(String[] args) throws IOException {
        String[] s = read.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m=Integer.parseInt(s[1]);
        for (int i = 1; i <= n; i++) Arrays.fill(g[i], 0x3f3f3f3f); //权值不超过10000
         int a,b,c;
         for(int i=1;i<=m;i++){
             String[] s1 = read.readLine().split(" ");
             a=Integer.parseInt(s1[0]);
             b=Integer.parseInt(s1[1]);
             c=Integer.parseInt(s1[2]);
             g[a][b]=Math.min(g[a][b],c);
         }
         int t=dijkstar();
         log.write(Integer.toString(t));
         log.flush();
    }
    static int dijkstar(){

      //  用一个 dist 数组保存源点到其余各个节点的距离，
        //  dist[i] 表示源点到节点 i 的距离。初始时，dist 数组的各个元素为无穷大。
        //用一个状态数组 state 记录是否找到了源点到该节点的最短距离，
        // state[i] 如果为真，则表示找到了源点到节点 i 的最短距离，state[i] 如果为假，则表示源点到节点 i 的最短距离还没有找到。初始时，state 各个元素为假。
        dist[1]=0;//原点离原点的距离为0
        //遍历 dist 数组，找到没有确定最短路径的节点中距离源点最近的点t
        for(int i=1;i<=n;i++){
            int t=-1;
            for(int j=1;j<=n;j++){
                if(!st[j]&&(t==-1||dist[j]<dist[t]))t=j;
            }
            //找到了没有确定最短路径的节点中距离原点最近的点t,
            //标记为找到了原点到该点的最短路径
            //用t更新其他点的距离
            for(int j=1;j<=n;j++){
                dist[j]=Math.min(dist[j],dist[t]+g[t][j]);
            }
            //
        }
        if(dist[n]==0x3f3f)return -1;
        return dist[n];
    }
}
